#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int QDataType;
typedef struct QListNode
{
    QDataType data;
    QListNode* next;
}QListNode;


typedef struct Queue
{
    QListNode* head;
    QListNode* tail;
};

void QueueInit(Queue* q)
{
    assert(q);
    q->head = nullptr;
    q->tail = nullptr;
}

void QueueDestroy(Queue* q)
{
    assert(q);
    QListNode* cur = q->head;
    while(cur)
    {
        QListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = nullptr;
}

void QueuePush(Queue* q, QDataType data)
{
    assert(q);

    QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
    if(newnode == nullptr)
    {
        printf("malloc fail!\n");
        exit(-1);
    }
    newnode->data = data;
    newnode->next = nullptr;
    if(q->head = nullptr)
    {      
        //链表为空.
        q->head = q->tail = newnode;
    }
    else
    {
        //改变尾指针.
        q->tail->next = newnode;
        q->tail = newnode;
    }
}

bool QueueEmpty(Queue* q)
{
    return q->head == q->tail;
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    if(q->head->next == nullptr)
    {
        //队列中只有一个结点:
        free(q->head);
        q->head = q->tail = nullptr;
    }
    else
    {
        QListNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
}

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    return q->head->data;
}

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    return q->tail->data;
}

int QueueSize(Queue* q)
{
    assert(q);

    QListNode* cur = q->head;
    int count = 0;

    while(cur)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

